BOJ

[Silver II] 욱제가 풀어야 하는 문제 - 18249

문제 링크

성능 요약

메모리: 38336 KB, 시간: 420 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 10월 9일 09:18:43

문제 설명

wo_okje의 Codeforces 레이팅은 언제나 민트에 머물러 있다. 블루를 가기 위해 대회에 참가한 욱제는 A번 문제와 B번 문제를 합해 3분 만에 풀어내는 데 성공하고야 말았다! 신나게 C번 문제로 넘어간 욱제는 다음 문제를 마주치고 말았다.

당신에게 그래프가 주어진다. 이 그래프는 자연수 N(1 ≤ N ≤ 191,229)으로 표현되며, 다음과 같은 정점과 간선을 가진다.

• 그래프에는 N개의 빨간색 정점이 있으며, 각 정점은 1, 2, ..., N의 번호를 가진다.
• 그래프에는 N개의 파란색 정점이 있으며, 각 정점은 1, 2, ..., N의 번호를 가진다.
• 1 ≤ i ≤ N인 자연수 i에 대해 빨간색 i번 정점과 파란색 i번 정점을 연결하는 간선이 존재한다.
• 2 ≤ i ≤ N인 자연수 i에 대해 빨간색 i-1번 정점과 파란색 i번 정점을 연결하는 간선이 존재한다.
• 2 ≤ i ≤ N인 자연수 i에 대해 빨간색 i번 정점과 파란색 i-1번 정점을 연결하는 간선이 존재한다.

서로 다른 두 간선이 끝점을 공유하지 않도록 정확히 N개의 간선을 고르는 방법의 수를 구하여라. 단, 수가 너무 커질 수 있으니 10⁹+7로 나눈 나머지를 출력하여라.

라는 내용의 문제를 1시간째 고민했지만 문제를 풀지 못해 블루를 가지 못할 것 같다는 생각이 든 wo_okje는 당신에게 몰래 도움을 요청했다. wo_okje를 위해 이 문제를 풀어주자!

입력

입력의 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 191,229)

이후 T개의 줄에 걸쳐 각각의 그래프를 나타내는 자연수 N이 주어진다. (1 ≤ N ≤ 191,229)

출력

문제에 대한 답을 한 줄에 하나씩 총 T개의 줄에 걸쳐 출력하여라.

소스 코드

• 욱제가 풀어야 하는 문제.java